package com.google.codejam.storecredit;

import com.google.codejam.core.test.ACodeJamTestCase;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Concrete implementation of the <code>ACodeJamTestCase</code> for the
 * "Store Credit" problem.
 */
public class StoreCreditTestCase extends ACodeJamTestCase
{
	private int                   store_credit;
	private int                   number_of_items;
	private Map<Integer, Integer> item_price_map;
	private String                result_string;

	/**
	 * Constructor to initialize the store credit, number of items and the
	 * <code>Map</code> (specifically <code>LinkedHashMap</code>) containing the
	 * item numbers and item value, used for lookup.
	 *
	 * @param store_credit <code>int</code> value for the Store Credit.
	 * @param number_of_items <int>int</int> value indicating the number of
	 * purchasable items.
	 */
	public StoreCreditTestCase(
			  int store_credit,
			  int number_of_items)
	{
		this.store_credit = store_credit;
		this.number_of_items = number_of_items;
		// we use a map since we we will not store all the item values (we ignore
		// item values that are larger than or equal to our credit). we set the
		// initial size to the number of items, we know it will never be larger
		// than that. We use the LinkedHashMap because it has suitable performance
		// characteristics, both when adding values to the map and iterating over
		// the entries.
		this.item_price_map = new LinkedHashMap<Integer, Integer>(
				  number_of_items);
	}

	/**
	 * Adds an item price (and position) to the collection of item prices.
	 *
	 * @param item_position <code>int</code> position of item.
	 * @param item_value <code>int</code> value (price) of item.
	 */
	private void addItemPrice(
			  int item_position,
			  int item_value)
	{
		this.item_price_map.put(item_position, item_value);
	}

	/**
	 * Parses the data string to extract the values of each item in the store.
	 * The item value is converted to an integer and stored along with the
	 * position (index) of the item in the store. We need to store the index as
	 * well since we do not necessarily store all the item values. We discard
	 * values that are larger or equal to the credit we have available.
	 *
	 * @param data_str <code>String</code> containing all the item price values.
	 */
	@Override
	public void parseDataString(String data_str)
	{
		String[] item_prices_arr = data_str.split(" ");

		for (int i = 0; i < number_of_items; i++)
		{
			int item_value = Integer.parseInt(item_prices_arr[i]);

			// only add items with a value less than our available credit
			if (item_value < this.store_credit)
			{
				addItemPrice(i + 1, item_value);
			}
		}
	}

	/**
	 * Solves this test case. This is achieved by iterating through the list of
	 * items twice and comparing each item with every other item in the list. We
	 * don't compare items with themselves, since you are not allowed to purchase
	 * one item twice. We stop iterating as soon as we have found a combination
	 * of two items with a combined value equal to our credit.
	 */
	@Override
	public void solve()
	{
		for (Map.Entry<Integer, Integer> entry_outer : item_price_map.entrySet())
		{
			for (Map.Entry<Integer, Integer> entry_inner : item_price_map.entrySet())
			{
				if (entry_outer.getKey().intValue() ==
						  entry_inner.getKey().intValue())
				{
					// we can't 'buy' the same item twice, so skip this scenario
					continue;
				}

				int outer_item_value = entry_outer.getValue();
				int inner_item_value = entry_inner.getValue();

				if (store_credit == outer_item_value + inner_item_value)
				{
					if (entry_outer.getKey() < entry_inner.getKey())
					{
						result_string =
								  entry_outer.getKey() + " " + entry_inner.getKey();
					}
					else
					{
						result_string =
								  entry_inner.getKey() + " " + entry_outer.getKey();
					}
					// correct combination found, stop iterating
					return;
				}
			}
		}
	}

	/**
	 * Returns the calculated result string produced by the <code>solve</code>
	 * method.
	 *
	 * @return <code>String</code> containing the result.
	 */
	@Override
	public String getResultString()
	{
		return super.getResultString() + result_string;
	}
}